package Demo04;

public class Main {
}

class Solution {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("()(())"));
    }

    public static int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        char[] arr = s.toCharArray();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == ')') {
                if (arr[i - 1] == '(') {
                    dp[i] = 2;
                    if (i - 2 >= 0 && arr[i - 2] == ')') {
                        dp[i] += dp[i - 2];
                    }
                } else {
                    if (i - dp[i - 1] - 1 >= 0 && arr[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (i - dp[i - 1] - 2 >= 0 && arr[i - dp[i - 1] - 2] == ')') {
                            dp[i] += dp[i - dp[i - 1] - 2];
                        }
                    }
                }
            }
        }
        int max = 0;
        for (int i : dp) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }
}